package SlidingWindow;

import org.junit.Test;

import java.util.Comparator;
import java.util.Deque;
import java.util.LinkedList;
import java.util.PriorityQueue;

/**
 * @Classname JZ59滑动窗口的最大值
 * @Description TODO
 * @Date 2023/2/18 14:54
 * @Created by xjl
 */
public class JZ59滑动窗口的最大值 {

    /**
     * @description 使用一个大顶堆来实现 但是将超时间
     * @param: nums
     * @param: k
     * @date: 2023/2/18 18:45
     * @return: int[]
     * @author: xjl
     */
    public int[] maxSlidingWindow1(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });
        int[] result = new int[nums.length - (k - 1)];
        int x = 0;
        // 将数据放置到queue中
        int index = 0;
        while (index < nums.length) {
            while (index < nums.length && (queue.isEmpty() || queue.size() != k)) {
                queue.add(nums[index++]);
            }
            result[x++] = queue.peek();
            queue.remove(nums[index - k]);
        }
        return result;
    }

    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0 || k == 0) {
            return new int[0];
        }
        // 构建一个双端队列
        Deque<Integer> deque = new LinkedList<>();
        // 表示最后的存储结果的大小
        int[] res = new int[nums.length - k + 1];
        for (int j = 0, i = 1 - k; j < nums.length; i++, j++) {
            // 删除 deque 中对应的 nums[i-1]
            if (i > 0 && deque.peekFirst() == nums[i - 1]) {
                deque.removeFirst();
            }
            // 保持 deque 递减
            while (!deque.isEmpty() && deque.peekLast() < nums[j]) {
                deque.removeLast();
            }
            deque.addLast(nums[j]);
            // 记录窗口最大值
            if (i >= 0) {
                res[i] = deque.peekFirst();
            }
        }
        return res;
    }

    public int[] maxSlidingWindow3(int[] nums, int k) {
        if (nums.length == 0 || k == 0) {
            return new int[0];
        }
        // 头部是最大的值 并保持单调递减。
        Deque<Integer> deque = new LinkedList<>();
        int[] res = new int[nums.length - k + 1];
        // 未形成窗口
        for (int i = 0; i < k; i++) {
            while (!deque.isEmpty() && deque.peekLast() < nums[i]) {
                deque.removeLast();
            }
            deque.addLast(nums[i]);
        }
        res[0] = deque.peekFirst();
        // 形成窗口后
        for (int i = k; i < nums.length; i++) {
            if (deque.peekFirst() == nums[i - k]) {
                deque.removeFirst();
            }
            while (!deque.isEmpty() && deque.peekLast() < nums[i]) {
                deque.removeLast();
            }
            deque.addLast(nums[i]);
            res[i - k + 1] = deque.peekFirst();
        }
        return res;
    }

    @Test
    public void test() {
        int[] ints = maxSlidingWindow1(new int[]{1}, 1);
    }
}
